package org.example.leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 51. N 皇后
 * 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
 * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 */
public class Code51 {
    List<List<String>> res = new ArrayList<>();
    char[][] board;

    public List<List<String>> solveNQueens(int n) {
        // 初始化棋盘
        board = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }

        res.clear(); // 清空结果集，保证多次调用的正确性
        backtracking(n, 0);
        return res;
    }

    private void backtracking(int n, int row) {
        if (row == n) {
            // 将char[][]转换为List<String>
            List<String> solution = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                solution.add(new String(board[i]));
            }
            res.add(solution);
            return;
        }

        for (int col = 0; col < n; col++) {
            if (isValid(col, row, n)) {
                // 放置皇后
                board[row][col] = 'Q';

                // 递归处理下一行
                backtracking(n, row + 1);

                // 回溯，恢复状态
                board[row][col] = '.';
            }
        }
    }

    /**
     * 检查在(row,col)位置放置皇后是否合法
     *
     * @param col 列索引
     * @param row 行索引
     * @param n   棋盘大小
     * @return 是否合法
     */
    private boolean isValid(int col, int row, int n) {
        // 检查列是否有皇后冲突
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }

        // 检查左上斜线是否有皇后冲突
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }

        // 检查右上斜线是否有皇后冲突
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }

        return true;
    }
}
